//合并两个排序的链表: https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?
//方法一，比较好理解的
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //不考虑头结点(其实，考虑头结点简单，我们按照难的来)
        //合并前，先判定
        if (nullptr == pHead1) {
            return pHead2;
        }
        if (nullptr == pHead2) {
            return pHead1;
        }
        //合并中,无非是比较各自首节点谁小，就把该节点从原链表中删除，在尾插到新节点处，比较中，两个链表任何一个都不能为空
        ListNode* new_head = nullptr;
        ListNode* new_tail = nullptr;
        while (pHead1 && pHead2) {
            //先判定拿那个节点
            ListNode* p = pHead1->val < pHead2->val ? pHead1 : pHead2;
            //再在指定链表中，删除目标节点
            if (p == pHead1) {
                pHead1 = pHead1->next;
            } else {
                pHead2 = pHead2->next;
            }
            //尾插到新链表,这里要考虑第一次插入的情况
            if (nullptr == new_head) {
                new_head = p;
                new_tail = p;
            } else {
                new_tail->next = p;
                new_tail = p;
            }
        }
//合并后，可能会有：1. pHead1为空 2. pHead2为空 3. 都为空(合并完成)
        if (nullptr == pHead1) {
            new_tail->next = pHead2;
        } else if (nullptr == pHead2) {
            new_tail->next = pHead1;
        } else {
//do nothing
        }
        return new_head;
    }
};
//方法二，上一道题是Java写的两种方法，我们这里来一个C++的
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
//不考虑头结点(其实，考虑头结点简单，我们按照难的来)
//合并前，先判定
        if (nullptr == pHead1) {
            return pHead2;
        }
        if (nullptr == pHead2) {
            return pHead1;
        }
//合并中，找到第一个节点
        ListNode* new_head = nullptr;
        if (pHead1->val < pHead2->val) {
            new_head = pHead1;
            pHead1 = pHead1->next;
        } else {
            new_head = pHead2;
            pHead2 = pHead2->next;
        }
//合并剩下的节点
        new_head->next = Merge(pHead1, pHead2);
        return new_head;
    }
};